package three;

public class A046 {



    //1.先序遍历每个节点都可以是根
    //2.拿着从前序遍历的根，到中序遍历中找到它的位置。然后以该位置，左边就是这个根的左子树，右边就是它的右子树
    //3.递归1.步
    //参数：构建的函数需要有一个范围，用来判断中序遍历的左右子树是否合法
    int preIndex = 0; //遍历前序遍历的下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode build(int[] preorder, int[] inorder,int start,int end) {
        if(start>end) return null;
        //1.根据前序建根
        //2.根据 root 将中序遍历分成两半
        //3.递归：重复1-2步
        TreeNode root = new TreeNode(preorder[preIndex++]);
        int index = search(inorder,start,end,root.val);
        root.left = build(preorder,inorder,start,index-1);
        root.right = build(preorder,inorder,index+1,end);
        return root;
    }
    public int search(int[] inorder,int start,int end,int key) {
        for(int i=start;i<=end;i++) {
            if(inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }
}
